package com.mianshi;

/**
 * 统计字符串中回文字符串的个数
 */
public class xingye {
    public static void main(String[] args) {
        System.out.println(cntPalindromicSubstrings("aaa"));
    }

    public static int cntPalindromicSubstrings (String s) {
        // write code here
        int len = s.length();
        int ans = 0;
        boolean[][] dp = new boolean[len][len];
        for(int i = len-1; i >=0; i--){
            for(int j = i; j < len; j++){
                dp[i][j] = ((s.charAt(i) == s.charAt(j)
                        && ((j-i < 3) || dp[i+1][j-1])));
                if(dp[i][j]){
                    ans++;
                }
            }
        }
        return ans;
    }
}
